home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / glibc108.zip / glibc108 / sysdeps / generic / mul.c < prev    next >
C/C++ Source or Header  |  1994-04-26  |  4KB  |  148 lines
  1. /* __mpn_mul -- Multiply two natural numbers.
  2.  
  3. Copyright (C) 1991, 1993, 1994 Free Software Foundation, Inc.
  4.  
  5. This file is part of the GNU MP Library.
  6.  
  7. The GNU MP Library is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU Library General Public License as published by
  9. the Free Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.
  11.  
  12. The GNU MP Library is distributed in the hope that it will be useful, but
  13. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  15. License for more details.
  16.  
  17. You should have received a copy of the GNU Library General Public License
  18. along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
  19. the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21. #include "gmp.h"
  22. #include "gmp-impl.h"
  23.  
  24. /* Multiply the natural numbers u (pointed to by UP, with USIZE limbs)
  25.    and v (pointed to by VP, with VSIZE limbs), and store the result at
  26.    PRODP.  USIZE + VSIZE limbs are always stored, but if the input
  27.    operands are normalized.  Return the most significant limb of the
  28.    result.
  29.  
  30.    NOTE: The space pointed to by PRODP is overwritten before finished
  31.    with U and V, so overlap is an error.
  32.  
  33.    Argument constraints:
  34.    1. USIZE >= VSIZE.
  35.    2. PRODP != UP and PRODP != VP, i.e. the destination
  36.       must be distinct from the multiplier and the multiplicand.  */
  37.  
  38. /* If KARATSUBA_THRESHOLD is not already defined, define it to a
  39.    value which is good on most machines.  */
  40. #ifndef KARATSUBA_THRESHOLD
  41. #define KARATSUBA_THRESHOLD 32
  42. #endif
  43.  
  44. mp_limb
  45. #if __STDC__
  46. __mpn_mul (mp_ptr prodp,
  47.       mp_srcptr up, mp_size_t usize,
  48.       mp_srcptr vp, mp_size_t vsize)
  49. #else
  50. __mpn_mul (prodp, up, usize, vp, vsize)
  51.      mp_ptr prodp;
  52.      mp_srcptr up;
  53.      mp_size_t usize;
  54.      mp_srcptr vp;
  55.      mp_size_t vsize;
  56. #endif
  57. {
  58.   mp_ptr prod_endp = prodp + usize + vsize - 1;
  59.   mp_limb cy;
  60.   mp_ptr tspace;
  61.  
  62.   if (vsize < KARATSUBA_THRESHOLD)
  63.     {
  64.       /* Handle simple cases with traditional multiplication.
  65.  
  66.      This is the most critical code of the entire function.  All
  67.      multiplies rely on this, both small and huge.  Small ones arrive
  68.      here immediately.  Huge ones arrive here as this is the base case
  69.      for Karatsuba's recursive algorithm below.  */
  70.       mp_size_t i;
  71.       mp_limb cy_limb;
  72.       mp_limb v_limb;
  73.  
  74.       if (vsize == 0)
  75.     return 0;
  76.  
  77.       /* Multiply by the first limb in V separately, as the result can be
  78.      stored (not added) to PROD.  We also avoid a loop for zeroing.  */
  79.       v_limb = vp[0];
  80.       if (v_limb <= 1)
  81.     {
  82.       if (v_limb == 1)
  83.         MPN_COPY (prodp, up, usize);
  84.       else
  85.         MPN_ZERO (prodp, usize);
  86.       cy_limb = 0;
  87.     }
  88.       else
  89.     cy_limb = __mpn_mul_1 (prodp, up, usize, v_limb);
  90.  
  91.       prodp[usize] = cy_limb;
  92.       prodp++;
  93.  
  94.       /* For each iteration in the outer loop, multiply one limb from
  95.      U with one limb from V, and add it to PROD.  */
  96.       for (i = 1; i < vsize; i++)
  97.     {
  98.       v_limb = vp[i];
  99.       if (v_limb <= 1)
  100.         {
  101.           cy_limb = 0;
  102.           if (v_limb == 1)
  103.         cy_limb = __mpn_add_n (prodp, prodp, up, usize);
  104.         }
  105.       else
  106.         cy_limb = __mpn_addmul_1 (prodp, up, usize, v_limb);
  107.  
  108.       prodp[usize] = cy_limb;
  109.       prodp++;
  110.     }
  111.       return cy_limb;
  112.     }
  113.  
  114.   tspace = (mp_ptr) alloca (2 * vsize * BYTES_PER_MP_LIMB);
  115.   MPN_MUL_N_RECURSE (prodp, up, vp, vsize, tspace);
  116.  
  117.   prodp += vsize;
  118.   up += vsize;
  119.   usize -= vsize;
  120.   if (usize >= vsize)
  121.     {
  122.       mp_ptr tp = (mp_ptr) alloca (2 * vsize * BYTES_PER_MP_LIMB);
  123.       do
  124.     {
  125.       MPN_MUL_N_RECURSE (tp, up, vp, vsize, tspace);
  126.       cy = __mpn_add_n (prodp, prodp, tp, vsize);
  127.       __mpn_add_1 (prodp + vsize, tp + vsize, vsize, cy);
  128.       prodp += vsize;
  129.       up += vsize;
  130.       usize -= vsize;
  131.     }
  132.       while (usize >= vsize);
  133.     }
  134.  
  135.   /* True: usize < vsize.  */
  136.  
  137.   /* Make life simple: Recurse.  */
  138.  
  139.   if (usize != 0)
  140.     {
  141.       __mpn_mul (tspace, vp, vsize, up, usize);
  142.       cy = __mpn_add_n (prodp, prodp, tspace, vsize);
  143.       __mpn_add_1 (prodp + vsize, tspace + vsize, usize, cy);
  144.     }
  145.  
  146.   return *prod_endp;
  147. }
  148.